// 抽象一个方法getNode用来获取某个索引下的节点，方便后续方法使用
// 时间复杂度：O(n)
// 空间复杂度：O(1)

function MyLinkedList() {
    this.size = 0
    this.head = null
    this.tail = null
}

function ListNode(val = 0, next = null) {
    this.val = val
    this.next = next
}

MyLinkedList.prototype.getNode = function (index) {
    if (index < 0 || index >= this.size) {
        return null
    }
    const dummyNode = new ListNode(0, this.head)
    let cur = dummyNode
    while (index >= 0) {
        cur = cur.next
        index--
    }
    return cur
}

MyLinkedList.prototype.get = function (index) {
    const node = this.getNode(index)
    if (!node) {
        return -1
    }
    return node.val
}

MyLinkedList.prototype.addAtHead = function (val) {
    if (!this.head) {
        this.head = new ListNode(val)
        this.tail = this.head
    } else {
        this.head = new ListNode(val, this.head) 
    }
    this.size++
}

MyLinkedList.prototype.addAtTail = function (val) {
    if (!this.tail) {
        this.tail = new ListNode(val)
        this.head = this.tail
    } else {
        const newNode = new ListNode(val)
        this.tail.next = newNode
        this.tail = newNode
    }
    this.size++
}

MyLinkedList.prototype.addAtIndex = function (index, val) {
    if (index > this.size) {
        return
    }
    if (index <= 0) {
        this.addAtHead(val)
    } else if (index === this.size) {
        this.addAtTail(val)
    } else {
        let node = this.getNode(index - 1)
        let newNode = new ListNode(val, node.next)
        node.next = newNode
        this.size++
    }
}

MyLinkedList.prototype.deleteAtIndex = function (index) {
    if (index < 0 || index >= this.size) {
        return
    }
    if (index === 0) {
        this.head = this.head.next
        if (this.size === 1) {
            this.tail = null
        }
        this.size--
    } else {
        const node = this.getNode(index - 1)
        node.next = node.next.next
        if (index === this.size - 1) {
            this.tail = node
        }
        this.size--
    }
}

// 链表类
function LinkedList(arr) {
    this.head = new ListNode(arr[0])
    let cur = this.head
    for (let i = 1; i < arr.length; i++) {
        let node = new ListNode(arr[i])
        cur.next = node
        cur =  cur.next
    }
}

module.exports = {
    ListNode,
    LinkedList
}
